#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <vector>

using namespace std;

/***
 * 2. 给出二叉树的二叉链表结构体,假设数据域为整数,编写算法査找二叉树中每一层的最大值
 * 层序遍历 求最大值
 * 层序遍历需要利用队列 与层序遍历稍微有点不同 因为需要求得每层的最大值 
 * 所以遍历时要区分每层 通过一个循环将每层的最大值求得并保存
 * */

typedef struct TNode
{
    int data;
    TNode *left;
    TNode *right;
} TNode, *Tree;

vector<int> GetLayerMaxNode(Tree &T)
{
    queue<TNode *> tmpQueue;
    vector<int> res;
    if (T == NULL)
        return res; // 二叉树为空 直接返回
    tmpQueue.push(T);
    while (!tmpQueue.empty())
    {
        int size = tmpQueue.size(); // 当前一层的队列大小
        int max = -2147483648;      // 当前一层的最大值
        for (int i = 0; i < size; i++)
        {
            TNode *node = tmpQueue.front();
            tmpQueue.pop();
            if (node->data > max)
                max = node->data;
            if (node->left) // 若左子树不为空, 入队
                tmpQueue.push(node->left);
            if (node->right) // 若右子树不为空, 入队
                tmpQueue.push(node->right);
        }
        res.push_back(max);
    }
    return res;
}

// 测试用
TNode *NewNode(int e)
{
    TNode *s = (TNode *)malloc(sizeof(TNode));
    s->data = e;
    s->left = NULL;
    s->right = NULL;
    return s;
}

int main(int argc, char const *argv[])
{
    Tree T;
    T = NewNode(0);
    T->left = NewNode(1);
    T->right = NewNode(2);
    T->left->left = NewNode(3);
    T->left->right = NewNode(4);
    T->right->left = NewNode(5);
    vector<int> res = GetLayerMaxNode(T);
    for (int i = 0; i < res.size(); i++)
        printf("第%d层最大值为 %d\n", i+1, res[i]);
    return 0;
}
